#include <iostream>
using namespace std;
#include <vector>
#include <string>

// return the max num of longest commom subsequence
// i j  ---  0~i  0~j
int process(string& str1 , string& str2 , int i , int j)
{
  // base case 
  if (i == 0 && j == 0)
  {
    return str1[i] == str2[j] ? 1 : 0;
  }

  if (i == 0)
  {
    if (str1[i] == str2[j])
    {
      return 1;
    }
    else 
    {
      return process(str1 , str2 , i , j-1);
    }
  }
  else if (j == 0)
  {
    if (str1[i] == str2[j])
    {
      return 1;
    }
    else 
    {
      return process(str1 , str2 , i - 1 , j);
    }
  }
  else  
  {
    // j != 0;
    // i != 0;
    // possible i  ... j
    int p1 = process(str1 , str2 , i - 1 , j);
    int p2 = process(str1 , str2 , i , j - 1);
    int p3 = str1[i] == str2[j] ? 1 + process(str1 , str2 , i -1 , j -1) : 0 ;

    return max(p1 , max (p2 , p3));
  }
}

int process1(string& str1, string& str2, vector<vector<int>>& dp)
{
  dp[0][0] = str1[0] == str2[0] ? 1 : 0;

  for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++)
  {
    dp[0][j] = str1[0] == str2[j] ?  1 : dp[0][j-1];
  }

  for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++)
  {
    dp[i][0] = str1[i] == str2[0] ? 1 : dp[i-1][0];
  }

  for (int i = 1 ; i < static_cast<int>(str1.size()) ; i++)
  {
    for (int j = 1 ; j < static_cast<int>(str2.size()) ; j++)
    {
      int p1 = dp[i-1][j];
      int p2 = dp[i][j-1];
      int p3 = str1[i] == str2[j] ? 1 + dp[i-1][j-1] : 0;

      dp[i][j] = max(p1 , max(p2 , p3));
    }
  }

  return dp[str1.size() - 1][str2.size() - 1];
}



int main()
{
  string s1 = "abc";
  string s2 = "abe";

  vector<vector<int>> dp(s1.size() , vector<int>(s2.size() , 0));
  cout <<  process1(s1 , s2 , dp) << endl;
  return 0;
}
